import java.util.*;

/**
* @description: 周赛307 t3
* @author hewei
* @date 2022/8/21 11:09
* @version 1.0
*/

public class AmountOfTime {

    HashMap<TreeNode, TreeNode> map;
    TreeNode target = null;
    int start;
    public int amountOfTime(TreeNode root, int start) {
        map = new HashMap<>();
        this.start = start;
        process(root);
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(target);
        HashSet<TreeNode> set = new HashSet<>();
        set.add(target);
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            ++count;
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (map.containsKey(poll)) {
                    TreeNode node = map.get(poll);
                    if (!set.contains(node)) {
                        queue.add(node);
                        set.add(node);
                    }
                }
                if (poll.left != null && !set.contains(poll.left)) {
                    set.add(poll.left);
                    queue.add(poll.left);
                }
                if (poll.right != null && !set.contains(poll.right)) {
                    set.add(poll.right);
                    queue.add(poll.right);
                }
            }
        }
        return count - 1;
    }

    public void process(TreeNode node) {
        if (node == null) return;

        if (node.left != null) {
            map.put(node.left, node);
        }
        if (node.right != null) {
            map.put(node.right, node);
        }
        if (node.val == start) target = node;
        process(node.left);
        process(node.right);
    }
}
